; SICP, 2.67
; Define an encoding tree and a sample message:

; (define sample-tree
;   (make-code-tree (make-leaf 'A 4)
;                   (make-code-tree
;                    (make-leaf 'B 2)
;                    (make-code-tree (make-leaf 'D 1)
;                                    (make-leaf 'C 1)))))

; (define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

; Use the decode procedure to decode the message, and give the result.

; The tree:
;      ABCD.8
;    /        \
;  A.4       BCD.4
;          /      \
;         B.2     DC.2
;               /      \
;             D.1      C.1

; The decoded message: ADABBCA

; SICP, 2.68
; The encode procedure takes as arguments a message and a tree and produces the
; list of bits that gives the encoded message.
;
; (define (encode message tree)
;   (if (null? message)
;     '()
;     (append (encode-symbol (car message) tree)
;             (encode (cdr message) tree))))
;
; Encode-symbol is a procedure, which you must write, that returns the list of
; bits that encodes a given symbol according to a given tree. You should design
; encode-symbol so that it signals an error if the symbol is not in the tree at
; all. Test your procedure by encoding the result you obtained in exercise 2.67
; with the sample tree and seeing whether it is the same as the original sample
; message.

(load "common.scm")

(define (element-of-set? x set)
  (element-of-list? x set eq?))

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? node)
  (eq? 'leaf (car node)))
(define (symbol-leaf node) (cadr node))
(define (weight-leaf node) (caddr node))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))
(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
  (if (leaf? tree)
    (list (symbol-leaf tree))
    (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
    (weight-leaf tree)
    (cadddr tree)))

; Version 1
(define (encode-symbol symbol tree)
  (cond
    ((leaf? tree) nil)
    ((element-of-set? symbol (symbols (left-branch tree)))
     (cons '0 (encode-symbol symbol (left-branch tree))))
    ((element-of-set? symbol (symbols (right-branch tree)))
     (cons '1 (encode-symbol symbol (right-branch tree))))
    (else
      (error "Bad symbol" symbol))))

; Version 2
(define (encode-symbol symbol tree)
  (if (not (element-of-set? symbol (symbols tree)))
    (error "Bad symbol" symbol)
    (cond
      ((leaf? tree) nil)
      ((element-of-set? symbol (symbols (left-branch tree)))
       (cons '0 (encode-symbol symbol (left-branch tree))))
      (else ; Note symbol must be in one of the branches.
       (cons '1 (encode-symbol symbol (right-branch tree)))))))

(define (encode message tree)
  (if (null? message)
    nil
    (append (encode-symbol (car message) tree)
            (encode (cdr message) tree))))

; See 2.67
(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                    (make-leaf 'B 2)
                    (make-code-tree
                      (make-leaf 'D 1)
                      (make-leaf 'C 1)))))

(define sample-message '(A D A B B C A))
(define sample-bad-message '(A D A B B G A))

(display
  (encode sample-message sample-tree))
(display
  (encode sample-bad-message sample-tree))
